package tree;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * @Author wangtengyu
 * @Create 2018-09-12-11:05
 *
 * 广度搜索遍历树 用到队列
 *
 * 从上到下打印二叉树 通过一个队列来辅助完成 第一次把根节点放入队列 之后每次把要打印出来的节点的左右子节点放入队列，这样就是按照自顶向下的顺序打印出来的了
 *
 * 如果太抽象的话，可以自己举例子或者画图
 */
public class PrintTreeFromTop {

  /**
   * 二叉树，按照行打印
   */
  public void printFromTop(TreeNode root) {
    Queue<TreeNode> queue = new LinkedBlockingQueue();
    if (root == null) {
      return;
    }
    queue.add(root);
    while (queue.size() > 0) {
      TreeNode treeNode = queue.remove();
      System.out.print(treeNode.getValue() + " ");
      if (treeNode.getLeft() != null) {
        queue.add(treeNode.getLeft());
      }
      if (treeNode.getRight() != null) {
        queue.add(treeNode.getRight());
      }
    }
  }

  /**
   * 二叉树按照行打印，并且每次打印完要换行 需要定义两个变量 第一个变量 waitPrintNum 当前要打印的数量 第二个变量 nextLineNum下一行要打印的数量
   */
  public void printFromTopAndChangeLine(TreeNode root) {
    if (root == null) {
      return;
    }
    Queue<TreeNode> queue = new LinkedBlockingQueue<>();
    queue.add(root);
    int waitPrintNum = 1;
    int nextLineNum = 0;
    while (queue.size() > 0) {
      TreeNode treeNode = queue.remove();
      System.out.print(treeNode.getValue() + " ");
      if (treeNode.getLeft() != null) {
        queue.add(treeNode.getLeft());
        nextLineNum++;
      }
      if (treeNode.getRight() != null) {
        queue.add(treeNode.getRight());
        nextLineNum++;
      }
      waitPrintNum--;

      if (waitPrintNum == 0) {
        System.out.println();
        waitPrintNum = nextLineNum;
        nextLineNum = 0;
      }


    }
  }


  public static void main(String[] args) {
    SimpleTreeCreator creator = new SimpleTreeCreator();
    TreeNode root = creator.createSampleTree();
    TreeNode leftroot = new TreeNode('A');
    leftroot.setLeft(new TreeNode('B'));
    leftroot.getLeft().setLeft(new TreeNode('C'));
    TreeNode rigthroot = new TreeNode('A');
    rigthroot.setRight(new TreeNode('B'));
    rigthroot.getRight().setRight(new TreeNode('C'));
    PrintTreeFromTop printTreeFromTop = new PrintTreeFromTop();
//        printTreeFromTop.printFromTop(root);
//        System.out.println();
//        printTreeFromTop.printFromTop(leftroot);
//        System.out.println();
//        printTreeFromTop.printFromTop(rigthroot);

    //分行打印
    printTreeFromTop.printFromTopAndChangeLine(root);


  }

}
